#include <iostream>
//#include "swordtooffer.h"
#include "sword2offer.h"
#include <vector>
using namespace std;
class Solution {
public:
	int maxSubArray(vector<int>& nums) {
		int fi, max = 0;
		for (int i = 0; i < nums.size(); ++i) {
			if (i == 0 || fi <= 0) {
				fi = nums[i];
			}
			else {
				fi += nums[i];
			}
			max = (fi > max) ? fi : max;
		}
		return max;
	}
};
void testSolution() {
	Solution s;
	vector<int> v = { -2,1,-3,4,-1,2,1,-5,4 };
	int m = s.maxSubArray(v);
	cout << "max is " << m << endl;
}
int main() {
	//testFindInMatrix();
	//testReplaceSpace();
	//testCount1s();
	//testPow();
	//testSwap();
	//testPartition();
	//testQuickSort();
	testSolution();
	return 0;
}